package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

// 将一个字符串哈希为uint32
type Hash func(data []byte) uint32

// 存储所有的哈希键
type Map struct {
	hash     Hash           // hash函数
	replicas int            // 虚拟节点倍数
	keys     []int          // 哈希环
	hashMap  map[int]string //虚拟节点与真实结点的映射表 键是虚拟节点的哈希值 值是真实节点的名称
}

func New(replicas int, fn Hash) *Map {
	// 采用依赖注入，能替换成自定义的哈希函数，默认使用crc32
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

// Add 添加真实节点
func (m *Map) Add(keys ...string) {
	// 允许传入0或多个真实节点的名称
	// 每一个真实节点对应创建m.replicas个虚拟节点，虚拟节点的名称是 strconv.Itoa(i)+key 通过添加编号的方式区分不同的虚拟节点
	for _, key := range keys {
		for i := 0; i < m.replicas; i++ {
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			// 将虚拟节点的哈希值添加到环上
			m.keys = append(m.keys, hash)
			// key 与 hash 的映射，key是真实节点的名称
			m.hashMap[hash] = key
		}
	}
	// 环上的哈希值排序
	sort.Ints(m.keys)
}

// Get 选择节点
func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		// 哈希环上没有虚拟节点
		return ""
	}
	// 先计算key的哈希值
	hash := int(m.hash([]byte(key)))
	// 顺时针找到第一个匹配的虚拟节点下标idx，从m.keys中获取对应哈希值
	// 如果idx==len(m.keys) 说明应该选择第一个虚拟节点，因为哈希环是循环的
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})
	// 通过哈希映射得到真实的节点
	return m.hashMap[m.keys[idx%len(m.keys)]]
}
